package algorithm.dynamic_programming;

import javax.print.DocFlavor;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class PrintAllPermutations {

    public static List<String> permutations(String s){
        ArrayList<String> list = new ArrayList<>();
        if(s == null || s.length() == 0){
            return list;
        }
        process1(s.toCharArray(), list, 0);
        return list;

    }

    public static void process1(char[] str, ArrayList<String> ans, int index){
        if(index ==  str.length){
            ans.add(String.valueOf(str));
            return;
        }
        for (int i = index; i < str.length; i++) {
            swap(str, index, i);
            process1(str, ans, index + 1);
            swap(str, index, i);
        }
    }

    public static ArrayList<String> NoRepeatedPermutations(String s){
        ArrayList<String> list = new ArrayList<>();
        if(s == null || s.length() == 0){
            return list;
        }
        process2(s.toCharArray(), list, 0);
        return list;

    }

    public static void process2(char[] str, ArrayList<String> ans, int index){
        if(index ==  str.length){
            ans.add(String.valueOf(str));
            return;
        }
        boolean[] visit = new boolean[26];
        for (int i = index; i < str.length; i++) {
            if(!visit[str[i] - 'a']){
                swap(str, index, i);
                process2(str, ans, index + 1);
                swap(str, index, i);
                visit[str[i] - 'a'] = true;
            }
        }
    }
    public static void swap(char[] str, int index1, int index2){
        char temp = str[index1];
        str[index1] = str[index2];
        str[index2] = temp;
    }

    public static void main(String[] args) {
        String s = "abc";
        List<String> list = permutations(s);
//        ArrayList<String> set = NoRepeatedPermutations(s);
        System.out.println(list);
      //  System.out.println(set);
    }

}
